#define _CRT_SECURE_NO_WARNINGS 1
bool cmp(string& a, string& b) {
    return a < b;
}
class Solution {
public:
    int find(int x, vector<int>& p) {
        if (x != p[x])p[x] = find(p[x], p);
        return p[x];
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        vector<int>p(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }

        unordered_map<string, int>mp;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                if (!mp.count(accounts[i][j])) {
                    mp[accounts[i][j]] = i;
                }
                else {
                    int a = find(i, p);
                    int b = find(mp[accounts[i][j]], p);
                    if (a == b)continue;
                    p[a] = b;
                }
            }
        }
        vector<vector<string>> arr(n);
        for (int i = 0; i < n; i++) {
            int a = find(i, p);
            for (int j = 1; j < accounts[i].size(); j++) {
                arr[a].push_back(accounts[i][j]);
            }
        }
        vector<vector<string>> ans;
        mp.clear();
        for (int i = 0; i < n; i++) {
            int a = find(i, p);
            if (a == i) {
                vector<string> t;
                t.push_back(accounts[i][0]);
                for (auto e : arr[i]) {
                    if (!mp.count(e)) {
                        t.push_back(e);
                        mp[e] = 1;
                    }
                }
                ans.push_back(t);
            }
        }
        for (auto& it : ans) {
            sort(it.begin() + 1, it.end(), cmp);
        }
        return ans;
    }
};